Intro to Crypto 1 - localo

Category: Crypto
Difficulty: Baby
Author: black-simon

Description

This is an introductory challenge for beginners which want to dive into the world of Cryptography. The three stages of this challenge will increase in difficulty. For an introduction to the first challenge visit the authors step by step guide.

For my new RSA key I used my own SecurePrimeService which definitely generates a HUGE prime!

Summery

The author provided a message.txt and a pubkey.pem
The message.txt contains just a number and the pubkey.pem is a public key. All we have to do is to decrypt the message.txt.

Solution

We need to factor N. Factordb has already fully factored it, one prime was quite small 622751. I wrote a small sage script to decrypt the message and got the flag.

import OpenSSL.crypto as crypto
from factordb.factordb import FactorDB

key = open("pubkey.pem","rb").read()
message = open("message.txt","rb").read()

key = crypto.load_publickey(crypto.FILETYPE_PEM, key)
numbers = key.to_cryptography_key().public_numbers()

N = numbers.n
E = numbers.e
C = int(message)

f = FactorDB(N)
f.connect()
if f.get_status() == "FF":
    factors = f.get_factor_list()
    if len(factors) != 2:
        print("invalid N")
        exit(1)
    P = factors[0]
    Q = factors[1]
    D = xgcd(E,(P - 1) * (Q - 1))[1]
    M = pow(C,D,N)
    print(hex(int(str(M))).replace("L","")[2:].decode('hex'))
else:
    print("Not fully factored")

Mitigation

• never roll your own crypto
• use large primes

Flag

CSCG{factorizing_the_key=pr0f1t}